/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *GetMiddle(ListNode *head)
    {
        ListNode *slow=head, *fast=head;
        while(fast->next&&fast->next->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode *head) //反转链表
    {
        ListNode *prev=nullptr; //前驱节点
        ListNode *cur=head;
        while(cur)
        {
            ListNode *nextTemp=cur->next;
            cur->next=prev;
            prev=cur;
            cur=nextTemp;
        }
        return prev;
    }

    void merge(ListNode *head1, ListNode *head2) //交叉合并链表
    {
        ListNode *p1=head1, *p2=head2;
        while(p1&&p2)
        {
            p1=head1->next; p2=head2->next;

            head1->next=head2;
            head1=p1;

            head2->next=head1; head2=p2;
        }
    }

    void reorderList(ListNode* head) {
        if(head==nullptr) return; //边界情况判断
        
        //得到中间端点
        ListNode* mid=GetMiddle(head);
        ListNode *head1=head, *head2=mid->next;
        mid->next=nullptr;
        
        //反转后半段连表
        head2=reverseList(head2);

        //合并两个链表
        merge(head1, head2);
    }
};